MDS array codes are widely used in storage systems to protect data againsterasures. We address the \emph{rebuilding ratio} problem, namely, in the caseof erasures, what is the fraction of the remaining information that needs to beaccessed in order to rebuild \emph{exactly} the lost information? It is clearthat when the number of erasures equals the maximum number of erasures that anMDS code can correct then the rebuilding ratio is 1 (access all the remaininginformation). However, the interesting and more practical case is when thenumber of erasures is smaller than the erasure correcting capability of thecode. For example, consider an MDS code that can correct two erasures: What isthe smallest amount of information that one needs to access in order to correcta single erasure? Previous work showed that the rebuilding ratio is boundedbetween 1/2 and 3/4, however, the exact value was left as an open problem. Inthis paper, we solve this open problem and prove that for the case of a singleerasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. Ingeneral, we construct a new family of $r$-erasure correcting MDS array codesthat has optimal rebuilding ratio of $\frac{e}{r}$ in the case of $e$ erasures,$1 \le e \le r$. Our array codes have efficient encoding and decodingalgorithms (for the case $r=2$ they use a finite field of size 3) and anoptimal update property.
展开▼
机译：MDS阵列代码广泛用于存储系统中，以防止数据遭到擦除。我们要解决\ emph {rebuilding ratio}问题，即在擦除的情况下，为了重建\ emph {确切地}丢失的信息而需要访问的剩余信息的比例是多少？显然，当擦除次数等于MDS代码可以纠正的最大擦除次数时，重建比率为1（访问所有剩余信息）。然而，有趣的和更实际的情况是当擦除次数小于代码的擦除校正能力时。例如，考虑一种可以纠正两个擦除的MDS代码：为了纠正一个擦除，一个人需要访问的最少信息量是多少？先前的工作表明，重建比例限制在1/2和3/4之间，但是，确切的值仍然是一个未解决的问题。在本文中，我们解决了这个开放问题，并证明了对于带有2擦除校正码的单擦除情况，重建比例为1/2。通常，我们构造了一个$ r $擦除校正MDS阵列代码新系列，在$ e $擦除的情况下，其最佳重建比率为$ \ frac {e} {r} $，$ 1 \ le e \ le r $。我们的数组代码具有有效的编码和解码算法（在$ r = 2 $的情况下，它们使用大小为3的有限字段）和最佳更新属性。
展开▼
